package _腾讯推荐._数组与字符串;

/**
 * @ClassName : _盛水最多的容器
 * @CreateTime : 2020/09/20 09
 * @Author : lerry_li
 * @Descrpition : 盛最多水的容器
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * 示例：
 * <p>
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 */
public class _盛水最多的容器 {
    /**
     * 解法1：暴力法 时间O(n^2) 空间O(1)
     */
    public int maxArea(int[] height) {
        if (height == null || height.length == 0)
            return 0;
        int n = height.length - 1;
        int max_area = Math.min(height[0], height[n]) * n;
        for (int i = 0; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int area = Math.min(height[j], height[i]) * (j - i);
                max_area = Math.max(max_area, area);
            }
        }
        return max_area;
    }

    /**
     * 解法2：双指针法 时间O(n) 空间O(1)
     * 对O(n)的算法写一下自己的理解，一开始两个指针一个指向开头一个指向结尾，此时容器的底是最大的，接下来随着指针向内移动，会造成容器的底变小，
     * 在这种情况下想要让容器盛水变多，就只有在容器的高上下功夫。 那我们该如何决策哪个指针移动呢？我们能够发现不管是左指针向右移动一位，
     * 还是右指针向左移动一位，容器的底都是一样的，都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，
     * 所以我们选择指针所指的高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会。
     */
    public int maxArea_doublePoint(int[] height) {
        if (height == null || height.length == 0)
            return 0;
        int n = height.length - 1;
        int max_area = Math.min(height[0], height[n]) * n;
        int l = 0, r = n;
        while (l < r) {
            int temp_area = Math.min(height[l], height[r]) * (r - l);
            max_area = Math.max(max_area, temp_area);
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return max_area;
    }
}
